#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

class Solution {
    typedef pair<int, int> PII;
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        int dr[] = { -1,1,0,0 }, dc[] = { 0,0,-1,1 };
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        queue<PII> q;
        q.push({ entrance[0], entrance[1] });
        vis[entrance[0]][entrance[1]] = 1;
        auto isExit = [&](int r, int c)->bool {
            return (r != entrance[0] || c != entrance[1]) &&
                maze[r][c] == '.' && (r == 0 || r == m - 1 || c == 0 || c == n - 1);
            };

        int ret = 0;
        while (!q.empty()) {
            int ct = q.size();
            ret++;
            while (ct--) {
                auto [r, c] = q.front();
                q.pop();
                for (int i = 0; i < 4; i++) {
                    int nr = r + dr[i], nc = c + dc[i];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && maze[nr][nc] == '.' && !vis[nr][nc]) {
                        if (isExit(nr, nc)) return ret;
                        q.push({ nr, nc });
                        vis[nr][nc] = 1;
                    }
                }
            }
        }
        return -1;
    }
};

int main() {
    Solution s;
	vector<vector<char>> maze = { {'+','+','.','+'},{'.','.','.','+'},{'+','+','+','.'} };
	vector<int> entrance = { 1,2 };
	cout << s.nearestExit(maze, entrance) << endl;
	return 0;
    }